/**
 * Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
 */
package com.xinpan.exercise;

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        if(s.length() < 2)
            return 0;
        
        int left = 0;
        int res = 0;
        int len = 0; 
        for(int i = 0; i < s.length(); i++)
        {
            if(s.charAt(i) == '(')
            {
                left++;
                len++;
            }
            else
            {
                left--;
                len++;
            }
                
            
            if(left == 0 && len > res)
                res = len;
            else if(left < 0)
            {
                left = 0;
                len = 0;
            }
        }
        
        int right = 0;
        len = 0;
        for(int i = s.length()-1; i >= 0; i--)
        {
            if(s.charAt(i) == ')')
            {
                right++;
                len++;
            }
            else
            {
                right--;
                len++;
            }
                
            
            if(right == 0 && len > res)
                res = len;
            else if(right < 0)
            {
                len = 0;
                right = 0;
            }
        }
        
        return res;
    }
    
    public int longestValidParentheses2(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s.length() <= 1)
            return 0;
            
        int len = s.length();
        int[] mark = new int[len];
        for(int i = 0; i < len; i++)
            mark[i] = (s.charAt(i) == ')' ? -1 : 1);
        
        boolean go = true;
        while(go)
        {
            go = false;
            for(int i = 0; i < len; i++)
            {
                while(mark[i] == 1)
                {
                    int pos = i++;
                    for(; i < len && mark[i] == 0; i++);
                    if(i == len)
                        break;
                    else if(mark[i] == -1)
                    {
                        mark[pos] = mark[i] = 0;
                        go = true;
                    }   
                }
            }
        }
        
        int max = 0;
        for(int i = 0; i < len; i++)
        {
            int cnt = 0;
            while(mark[i] == 0) 
            {
                cnt++;
                i++;
            }
            if(cnt > max)
                max = cnt;
        }
        return max;
            
    }
   
}
